from typing import *
from math import inf


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [[0] * k for _ in range(k)]
        for num in nums:
            p = f[num % k].copy()
            for i in range(k):
                c = (i + num) % k
                p[c] = max(f[i][c] + 1, p[c])
            f[num % k] = p.copy()
        ans = 0
        for i in range(k):
            ans = max(ans, max(f[i]))
        return ans


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [[0] * k for _ in range(k)]
        for num in nums:
            for i in range(k):
                c = (i + num) % k
                f[num % k][c] = f[i][c] + 1
        ans = 0
        for i in range(k):
            ans = max(ans, max(f[i]))
        return ans


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [[0] * k for _ in range(k)]
        for num in nums:
            for i in range(k):
                c = (i + num) % k
                f[num % k][c] = f[i][c] + 1
        return max(map(max, f))


s = Solution()
print(s.maximumLength([3, 6], 5))
print(s.maximumLength(nums=[1, 2, 3, 4, 5], k=2))
print(s.maximumLength(nums=[1, 4, 2, 3, 1, 4], k=3))
